
<!DOCTYPE html>



<script src="https://code.jquery.com/jquery-3.3.1.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css">




  


<html class="theme-next gemini use-motion" lang="zh-Hans">

<head><meta name="generator" content="Hexo 3.8.0">
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><script src="https://crab-in-the-northeast.github.io/live2d/autoload.js"></script>
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">
<script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script>
<link href="//cdn.bootcss.com/pace/1.0.2/themes/pink/pace-theme-flash.css" rel="stylesheet">
<style>
    .pace .pace-progress {
        background: #1E92FB;
        height: 3px;
    }
    .pace .pace-progress-inner {
         box-shadow: 0 0 10px #1E92FB, 0 0 5px     #1E92FB;
    }
    .pace .pace-activity {
        border-top-color: #1E92FB;
        border-left-color: #1E92FB;   
    }
</style>








<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">










  <meta name="baidu-site-verification" content="b5DAJuWf3i">







  
  
  <link href="/blog/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/blog/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="https://crab-in-the-northeast.github.io/images/favicon.ico?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="https://crab-in-the-northeast.github.io/images/favicon.ico?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="https://crab-in-the-northeast.github.io/images/favicon.ico?v=5.1.4">


  <link rel="mask-icon" href="https://crab-in-the-northeast.github.io/images/favicon.ico?v=5.1.4" color="#222">





  <meta name="keywords" content="algorithms,">










<meta name="description" content="前言 还有，这个美化博客这个事情，大家还是时刻适可而止的好，不然永远没有尽头，把自己的大好时光全都浪费（滑稽.jpg）  这是一位dalao对美化blog的看法。最近，我美化了我的blog.但是文章很少，为了避免华而不实 （就是因为我懒）  ，我决定从今天开始更文啦~ （安利一个链接）   OI知识树 排序源代码下载 想用迅雷下载？https://crab-in-the-northeast.git">
<meta name="keywords" content="algorithms">
<meta property="og:type" content="article">
<meta property="og:title" content="排序大冒险（更新ing）">
<meta property="og:url" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/index.html">
<meta property="og:site_name" content="blog-东北小蟹蟹">
<meta property="og:description" content="前言 还有，这个美化博客这个事情，大家还是时刻适可而止的好，不然永远没有尽头，把自己的大好时光全都浪费（滑稽.jpg）  这是一位dalao对美化blog的看法。最近，我美化了我的blog.但是文章很少，为了避免华而不实 （就是因为我懒）  ，我决定从今天开始更文啦~ （安利一个链接）   OI知识树 排序源代码下载 想用迅雷下载？https://crab-in-the-northeast.git">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/menu-origin.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/counting.gif">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/stable.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/radix.gif">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/bubble.gif">
<meta property="og:image" content="https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=f469bce5077b020818c437b303b099b6/bf096b63f6246b60965c2634e6f81a4c510fa224.jpg">
<meta property="og:image" content="https://latex.codecogs.com/png.latex?\log_{2}{1000}">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/quick.gif">
<meta property="og:image" content="https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=ac41536b9016fdfacc61cebcd5e6e731/a9d3fd1f4134970a3be0b86f98cad1c8a6865dda.jpg">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/selection.gif">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap1.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap2.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap3.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap4.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap5.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap6.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap7.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap8.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap9.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap10.png">
<meta property="og:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/heap.gif">
<meta property="og:updated_time" content="2019-03-16T14:48:04.612Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="排序大冒险（更新ing）">
<meta name="twitter:description" content="前言 还有，这个美化博客这个事情，大家还是时刻适可而止的好，不然永远没有尽头，把自己的大好时光全都浪费（滑稽.jpg）  这是一位dalao对美化blog的看法。最近，我美化了我的blog.但是文章很少，为了避免华而不实 （就是因为我懒）  ，我决定从今天开始更文啦~ （安利一个链接）   OI知识树 排序源代码下载 想用迅雷下载？https://crab-in-the-northeast.git">
<meta name="twitter:image" content="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/menu-origin.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主 author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"你想找什么呀？蟹蟹帮你找找看~","hits_empty":"蟹蟹翻箱倒柜，也没找到你想找到的 ${query}，换个关键字让蟹蟹再找找看？","hits_stats":"嘿嘿，蟹蟹帮你找到了${hits}个结果，用了${time}毫秒，嘻嘻~"}
    }
  };
</script>




  <link rel="canonical" href="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/">




！
  <title>排序大冒险（更新ing） | blog-东北小蟹蟹</title>
  








  <style>
  canvas {
        position: fixed;
        top: 0;
        left: 0;
        width: 100%;
        height: 100%;
        z-index: 99999;
        background: rgba(125,137,95,0.1);
        pointer-events: none;
  }
  </style><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</head>
<canvas id="Snow" width="1233" height="380">
</canvas>
<center> <iframe scrolling="no" frameborder="no" clocktype="html5" style="overflow:hidden;border:0;margin:0;padding:0;width:356px;height:180px;" src="https://www.clocklink.com/html5embed.php?clock=042&timezone=CCT&color=blue&size=356&Title=&Message=&Target=&From=2019,1,1,0,0,0"></iframe> </center>

<br>
<center><h1 style="font-family:楷体" id="content"><span id="jinrishici-content"></span></h1></center>
<br>
<center><h1 style="font-family:楷体" id="from">出自【<span id="jinrishici-dynasty"></span>】<span id="jinrishici-author"></span>《<span id="jinrishici-title"></span>》</h1></center>
<script>
var x=document.getElementById("content");
x.style.color="White";
var y=document.getElementById("from");
y.style.color="White";
</script>
<script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>
<script type="text/javascript">
  jinrishici.load(function(result) {
    document.getElementById('jinrishici-content').style.fontSize = "30px"
    document.getElementById('jinrishici-content').innerText = result.data.content
    document.getElementById('jinrishici-dynasty').innerText = result.data.origin.dynasty
    document.getElementById('jinrishici-author').innerText = result.data.origin.author
    document.getElementById('jinrishici-title').innerText = result.data.origin.title
  });
</script> 
<body itemscope="" itemtype="//schema.org/WebPage" lang="zh-Hans">
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta name="referrer" content="unsafe-url">
  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>
    <a href="https://github.com/crab-in-the-northeast"><img width="149" height="149" style="position: absolute; top: 0; right: 0; border: 0;" src="https://github.blog/wp-content/uploads/2008/12/forkme_right_darkblue_121621.png?resize=149%2C149" class="attachment-full size-full" alt="Fork me on GitHub" data-recalc-dims="1"></a>
    <header id="header" class="header" itemscope="" itemtype="//schema.org/WPHeader">
      <div class="header-inner"><!-- 公告栏时钟控件 -->


<!-- 加载样式 -->

<link rel="stylesheet" type="text/css" href="https://crab-in-the-northeast.github.io/live2d/waifu.css">
<div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">blog-东北小蟹蟹</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">假如代码欺骗了你，<br>不要悲伤，不要心急！<br>因为代码还会接着欺骗你。</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/blog/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页 home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/blog/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于 about
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/blog/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签 tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/blog/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类 categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档 archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-commonweal">
          <a href="/blog/collections/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br>
            
            收藏 collections
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>
            
            搜索 search
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="你想找什么呀？蟹蟹帮你找找看，嘻嘻~" spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
 

</nav>



<!-- 小老鼠游戏控件 -->
 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://crab-in-the-northeast.gitee.io/blog/blog/algorithms/all_sorts/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="东北小蟹蟹">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/blog/images/kkksc03.gif">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="blog-东北小蟹蟹">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">排序大冒险（更新ing）</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-01-30T08:00:00+08:00">
                2019-01-30
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">更新于&#58;</span>
              
              <time title="更新于" itemprop="dateModified" datetime="2019-03-16T22:48:04+08:00">
                2019-03-16
              </time>
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/algorithms/" itemprop="url" rel="index">
                    <span itemprop="name">algorithms</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/blog/algorithms/all_sorts/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/blog/algorithms/all_sorts/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  9.2k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  35
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h1 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h1><blockquote>
<p>还有，这个美化博客这个事情，大家还是时刻适可而止的好，不然永远没有尽头，把自己的大好时光全都浪费（滑稽.jpg）</p>
</blockquote>
<p>这是一位<code>dalao</code>对美化<code>blog</code>的看法。<br>最近，我美化了我的<code>blog</code>.但是文章很少，为了避免华而不实<del> （就是因为我懒） </del> ，我决定从今天开始更文啦~</p>
<p>（<a href="https://www.luogu.org/problemnew/show/P1177" target="_blank" rel="noopener">安利一个链接</a>）  </p>
<p><a href="http://naotu.baidu.com/file/ee2e86d228a4cb74a949e44ac827f8a4?token=f983d0aef7a2f1ea" target="_blank" rel="noopener">OI知识树</a></p>
<p><a href="https://crab-in-the-northeast.github.io/downloads/all_sorts_code.zip" target="_blank" rel="noopener">排序源代码下载</a></p>
<p>想用迅雷下载？<br><a href="https://crab-in-the-northeast.github.io/downloads/all_sorts_code.zip" target="_blank" rel="noopener">https://crab-in-the-northeast.github.io/downloads/all_sorts_code.zip</a>  </p>
<p>声明：本篇文章为东北小蟹蟹原创，部分图片从<a href="baike.baidu.com">百度百科</a>搬来。转载不用跟我说，但请附上原文地址。</p>
<p>阅读本文你需要：  </p>
<ul>
<li>有一个对编程良好的态度  </li>
<li>对事物有好奇心  </li>
<li>会C++基础语法 </li>
</ul>
<p>本文中，目录及包含关系是按这个图安排的：  </p>
<p><img src="/blog/algorithms/all_sorts/menu-origin.png" alt="image"></p>
<p>其中，非线性时间比较类排序在本文中叫“基于比较的排序”，“线性时间非比较类排序”在本文中叫“基于计数的排序”。</p>
<p>注：所有文章都由我真实学习编程的过程而改编。</p>
<h1 id="背景"><a href="#背景" class="headerlink" title="背景"></a>背景</h1><p>我出生在一片沙滩。（当然这句话在现实生活中不是真的）  </p>
<p>我<code>7</code>岁的时候开始学习编程，然而……</p>
<p>两年之后……</p>
<p>一个阴雨连绵的日子。<br>真是奇怪，为什么沙滩还会下这么大的雨？不过，我也没多想，在用废弃的稿纸和在外面捡的木材啥的造好了一间屋子，我正在家里刷题。<br>突然，一个螃蟹找到了我。<br>他自称他叫“小排”，然后领我带到了一个隧道，<br>有一个紧锁的门。门上写着：<br><code>1,4,5,6,8,2,8.</code><br>上面有一个牌子，写着“谁要是通过了这个隧道，就可以获得无价之宝”。<br>右边是一台迷你计算机，左面的墙壁写了一个很大的<code>&quot;sort&quot;.</code><br>我顿时明白了，原来是让我们编辑代码来把数字排序啊！<br>门上还刻有两行英文：<br><code>You can&#39;t use the same kinds of sorts in two or more levels.</code><br><code>And, your program must end in 1s. Because your program must end in 1s in noip, too.</code><br>（每一关都要用不同种类的排序，<strong>时限1s</strong>，因为在<code>noip</code>中，每道题的时限一般均为<code>1s</code>）<br>于是，我便和小伙伴踏上了冒险之路。。。。<br>(<code>ps</code>:不要管螃蟹是怎么打字的)</p>
<h1 id="冒险开始了！"><a href="#冒险开始了！" class="headerlink" title="冒险开始了！"></a>冒险开始了！</h1><h2 id="基于计数的排序-counting"><a href="#基于计数的排序-counting" class="headerlink" title="基于计数的排序 counting"></a>基于计数的排序 <code>counting</code></h2><h3 id="计数排序-counting-sort"><a href="#计数排序-counting-sort" class="headerlink" title="计数排序 counting sort"></a>计数排序 <code>counting sort</code></h3><h4 id="概念-conception"><a href="#概念-conception" class="headerlink" title="概念 conception"></a>概念 <code>conception</code></h4><p>“这怎么办？” 小排抱怨。<br>我沉默不语，在沙滩下画上了<code>8</code>个格子。<br>小排好奇地瞅着我，问道：“这是什么意思呀？”<br>“你看，牌子上的数组是<code>1,4,5,6,8,2,8</code>吧。”<br>“嗯嗯。”<br>“这些格子的初始值都是<code>0</code>哈，首先来访的是<code>1</code>，所以我把第一个格子的数值<code>+1</code>.”<br>“嗯。这个时候<code>8</code>个格子分别为<code>1,0,0,0,0,0,0,0</code>了。”<br>“然后又来了<code>4</code>，所以我们把第四个……”<br>他迫不及待地把第四个格子里填了<code>1</code>.看来他还是挺聪明的。<br>他也不把用来写字的树枝还给我。不过我很开心，因为他明白了。<br>“可是到达第<code>7</code>个数，<code>8</code>已经是<code>1</code>了，怎么搞？”<br>“那你就再<code>+1</code>呗。”<br>于是，格子里的数字分别是<br>“<code>1,1,0,1,1,1,0,2</code>”<br>“所以你到底要干甚？”<br>“你想想看~”<br>他深思熟虑了片刻。你也思考思考吧~答案请往下翻。<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">S</span><br><span class="line">l</span><br><span class="line">i</span><br><span class="line">d</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">d</span><br><span class="line">o</span><br><span class="line">w</span><br><span class="line">n</span><br><span class="line"></span><br><span class="line">t</span><br><span class="line">o</span><br><span class="line"></span><br><span class="line">s</span><br><span class="line">e</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">n</span><br><span class="line">e</span><br><span class="line">x</span><br><span class="line">t</span><br><span class="line"></span><br><span class="line">p</span><br><span class="line">a</span><br><span class="line">g</span><br><span class="line">e</span><br><span class="line">!</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br></pre></td></tr></table></figure></p>
<p>他顿时大<del>雾</del>悟，明白了<del>OI的难度</del>。<br>“我们只要从第一个格子开始遍历，然后输出这个格子所对应的值次的下标，就可以排序了！”<br>“<code>bingo！</code>这就是计数排序，完美~”<br>鉴于小排的语文并不好，这里我再解释一下：<br>现在我们有了<code>8</code>个格子。<br>刚才说过格子里的数字分别是<br>“<code>1,1,0,1,1,1,0,2</code>”  </p>
<ul>
<li>第一个，<code>值是1，下标是1</code>，所以输出<code>1</code>次<code>1</code>，输出了<code>1</code>  </li>
<li>第二个，<code>值是1，下标是2</code>，所以输出<code>1</code>次<code>2</code>，输出了<code>2</code>  </li>
<li>第三个，<code>值是0，下标是3</code>，不输出  </li>
<li>第四个，<code>值是1，下标是4</code>，所以输出<code>1</code>次<code>4</code>，输出了<code>4</code>  </li>
<li>第五个，<code>值是1，下标是5</code>，所以输出<code>1</code>次<code>5</code>，输出了<code>5</code>  </li>
<li>第六个，<code>值是1，下标是6</code>，所以输出<code>1</code>次<code>6</code>，输出了<code>6</code>  </li>
<li>第七个，<code>值是0，下标是7</code>，不输出  </li>
<li><strong>第八个</strong>，<code>值是2，下标是8</code>，所以输出<code>2</code>次<code>8</code>，输出了<code>8 8</code></li>
</ul>
<p>尤其是 <strong>第八个</strong> 要格外小心。<br>所以输出了<code>1 2 4 5 6 8 8</code>.</p>
<p>哇，这是我们学习的第一个排序算法，干杯~</p>
<p><img src="/blog/algorithms/all_sorts/counting.gif" alt="image"></p>
<h4 id="代码-code"><a href="#代码-code" class="headerlink" title="代码 code"></a>代码 <code>code</code></h4><p>代码就很显然了，如下：<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> a[<span class="number">10005</span>];<span class="comment">//假设数列中最大值为10000，防爆+5.</span></span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;   <span class="comment">//一共有多少个数？</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> k;</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;k;<span class="comment">//输入当前的值</span></span><br><span class="line">        a[k]++;<span class="comment">//对应位置自增</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;=<span class="number">10005</span>;i++)</span><br><span class="line">        <span class="keyword">if</span>(a[i])<span class="comment">//如果存在这个数</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=a[i];j++)<span class="comment">//输出多少次呢？</span></span><br><span class="line">                <span class="built_in">cout</span>&lt;&lt;i&lt;&lt;<span class="string">' '</span>;<span class="comment">//输出这个数</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h4 id="练习-practicing"><a href="#练习-practicing" class="headerlink" title="练习 practicing"></a>练习 <code>practicing</code></h4><p>再实现一次倒序。<br>提示：很简单，倒着遍历就行了~</p>
<h4 id="分析-analysis"><a href="#分析-analysis" class="headerlink" title="分析 analysis"></a>分析 <code>analysis</code></h4><p>这个算法的正确性毋庸置疑，那么复杂度呢？<br>我们设k为数组中的最大值。<br><strong>时间复杂度</strong> 是<code>O(n+k)</code>，时间复杂度较低。<br><strong>空间复杂度</strong> 也是<code>O(k)</code>，那么这是优点还是缺点？留个悬念，一会讲。<br>果然，小排知道了计数排序的优点之后，就觉得计数排序无敌了！<br>计数排序是很好，因为 <strong>时间复杂度</strong> 很低。<br>但是没有任意一个算法是无敌的，<code>OI</code>算法的水深，他不被淹是不知道的。<br>所以，我考验他一下，<br>还是排序。数列变成了这样：<br><code>-2122,9.990,2147483646,13131314,123456789,-123123123</code><br><del> 真是极品数据 </del><br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure></p>
<p>果然他又哭着找我了，说我欺负它。<br>原因嘛你懂得，不懂你模拟一下就有<code>bug</code>了。<br>这里再顺便说一下，这个排序算法是<strong>稳定排序</strong>。<br>“东北小蟹蟹，什么是<strong>稳定排序</strong>啊？”<br>“如果原数列有两个值是一样的，并且排序后，这两个值的相邻关系<strong>一定</strong>不变，就是一开始排序的两个等值谁在前谁在后，排序后<strong>一定</strong>还是那个在前的在前，在后的在后，那么这个排序就是<strong>稳定排序</strong>，如果不能保证这个关系，则是<strong>不稳定排序</strong>。由于，你把数扔进对应的格子里，计数器+1，则从前往后遍历，<strong>一定顺序不变</strong>。所以，这个排序是<strong>稳定排序</strong>。并且我们要注意<strong>不稳定</strong>指的是未知，有可能还是原来的顺序，但是有可能就不是。不懂这个也没有关系，重要的是思维。”<br><img src="/blog/algorithms/all_sorts/stable.png" alt=""><br>啰嗦了这么多，现在我们来总结一下计数排序：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">计数排序的优点：</span><br><span class="line">时间复杂度低。</span><br><span class="line">计数排序的缺点：</span><br><span class="line">对数据要求比较高。</span><br></pre></td></tr></table></figure></p>
<p>哦，对了，就算数组不会爆炸，特大的数据会导致时间复杂度中<code>O(n+k)</code>都会炸。</p>
<h3 id="基数排序-radix-sort"><a href="#基数排序-radix-sort" class="headerlink" title="基数排序 radix sort"></a>基数排序 <code>radix sort</code></h3><h4 id="概念-conception-1"><a href="#概念-conception-1" class="headerlink" title="概念 conception"></a>概念 <code>conception</code></h4><p>大门打开了~<br>我们来到了<code>第2关</code>。<br>数列是这样的：<br><code>123,98,141,313,344</code><br>那么……  </p>
<p>“小排，你过来看。” 我把小排叫过来。<br>“嗯嗯。东北小蟹蟹，你又有啥思路了？”<br>“这个和计数排序差不多。首先我们定义<code>10</code>个格子，为了更形象一点，我们说成‘桶’。”<br>“然后你看见这几个数了吧，我们按个位把它丢进相应的桶。”<br>“什么玩意儿？？？”<br>“你看，第一个来的是<code>123</code>，个位是<code>3</code>，所以我们把它丢进3号桶。”<br>“哦哦！那其他的照样丢呗~”<br>“对滴！丢完后变成这样：”<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">0号桶：空</span><br><span class="line">1号桶：141</span><br><span class="line">2号桶：空</span><br><span class="line">3号桶：123,313（按顺序丢）</span><br><span class="line">4号桶：344</span><br><span class="line">5号桶：空</span><br><span class="line">6号桶：空</span><br><span class="line">7号桶：空</span><br><span class="line">8号桶：98</span><br><span class="line">9号桶：空</span><br></pre></td></tr></table></figure></p>
<p>“好了，我们再按照计数排序的思路依次取出这些数。”<br>“这个数列就变成了：<code>141,123,313,344,98.</code>”<br>“对对！个位已经排好序了。”小排<del>机敏地</del>回应。<br>“所以再按照刚才的思路排十位。”<br>“我来吧我来吧！”他又抢过了树枝。<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">0号桶：空</span><br><span class="line">1号桶：313</span><br><span class="line">2号桶：123</span><br><span class="line">3号桶：空</span><br><span class="line">4号桶：144,344</span><br><span class="line">5号桶：空</span><br><span class="line">6号桶：空</span><br><span class="line">7号桶：空</span><br><span class="line">8号桶：空</span><br><span class="line">9号桶：98.</span><br></pre></td></tr></table></figure></p>
<p>“再依次取出。”<br><code>313,123,144,344,98.</code><br>“接下来我全都知道了！！！”小排兴奋地大叫。<br>“再把百位排一遍。”<br>这该怎么排？请你自己试一试吧~<br>(ps:98的百位是<code>0</code>)<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">S</span><br><span class="line">l</span><br><span class="line">i</span><br><span class="line">d</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">d</span><br><span class="line">o</span><br><span class="line">w</span><br><span class="line">n</span><br><span class="line"></span><br><span class="line">t</span><br><span class="line">o</span><br><span class="line"></span><br><span class="line">s</span><br><span class="line">e</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">n</span><br><span class="line">e</span><br><span class="line">x</span><br><span class="line">t</span><br><span class="line"></span><br><span class="line">p</span><br><span class="line">a</span><br><span class="line">g</span><br><span class="line">e</span><br><span class="line">!</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br></pre></td></tr></table></figure></p>
<p>如果你算得没错，答案应该是：<br><code>98,123,144,313,344.</code><br>“哎？这怎么就变有序了？”<br>“嗯。这个排序就叫做基数排序。也是很好用滴。”  </p>
<p>刚才提到了桶，顺便提一下，其实桶排序，基数排序和计数排序都是差不多的，但也有区别，一会我们会讲的~  </p>
<p>并且，刚才所讲的基数排序，使用的是<code>LSD (Least Significant Digit first)</code> 是从低位到高位分配。<br>还有一个<code>MSD (Most Significant Digit first)</code> 是从高位到低位分配。这比<code>LSD</code>要麻烦许多，这里就不再赘述了。    </p>
<p><img src="/blog/algorithms/all_sorts/radix.gif" alt="image"></p>
<h4 id="代码-code-1"><a href="#代码-code-1" class="headerlink" title="代码 code"></a>代码 <code>code</code></h4><p>这个代码比计数排序要难得多，其中用了<code>STL</code>.<br>当然，我并不是说计数排序不能突破<code>STL</code>的限制，你可以自己试试看不用<code>STL</code>的解法。<br>没有看懂的可以直接跳过这里，这个代码不重要。<br>重要的是思路和原理。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">getlen</span><span class="params">(<span class="keyword">int</span> n)</span><span class="comment">//获取一个数的长度</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ret=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(n)</span><br><span class="line">    &#123;</span><br><span class="line">        n/=<span class="number">10</span>;<span class="comment">//n不断除以10</span></span><br><span class="line">        ret++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; bucket[<span class="number">10</span>];<span class="comment">//用了STL</span></span><br><span class="line"><span class="keyword">int</span> n,a[<span class="number">10</span>],tmp[<span class="number">10</span>],maxlen,bk,divpos=<span class="number">1</span>;</span><br><span class="line"><span class="comment">//有n个数，第i个数是a[i]，tmp是临时数组</span></span><br><span class="line"><span class="comment">//maxlen是数组中最大数的长度，bk是数组下标的遍历</span></span><br><span class="line"><span class="comment">//divpos用来变化求一个数的每一位</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">        maxlen=max(maxlen,getlen(a[i]));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//以上都是读入</span></span><br><span class="line">    <span class="keyword">while</span>(maxlen--)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">10</span>;i++)</span><br><span class="line">            bucket[i].clear();<span class="comment">//初始化</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">            bucket[a[i]/divpos%<span class="number">10</span>].push_back(a[i]);<span class="comment">//将数扔进对应的桶</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">10</span>;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt;::iterator iter=bucket[i].begin();</span><br><span class="line">            <span class="keyword">for</span>(;iter!=bucket[i].end();iter++)</span><br><span class="line">                tmp[bk++]=(*iter);</span><br><span class="line">            <span class="comment">//用iterator遍历，把这些数再重新取出</span></span><br><span class="line">        &#125;</span><br><span class="line">        bk=<span class="number">0</span>;<span class="comment">//初始化下标遍历变量bk</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)<span class="comment">//将临时数组赋值到a数组</span></span><br><span class="line">            a[i]=tmp[i];</span><br><span class="line">        divpos*=<span class="number">10</span>;<span class="comment">//变化divpos求出下一位</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;a[i]&lt;&lt;<span class="string">' '</span>;<span class="comment">//输出</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h4 id="练习-practicing-1"><a href="#练习-practicing-1" class="headerlink" title="练习 practicing"></a>练习 <code>practicing</code></h4><p>排序：第一行为数据个数，第二行为数据。<br>输入：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">9</span><br><span class="line">999 1083 4194 5141 5341 4654 4245 1312 3543</span><br></pre></td></tr></table></figure></p>
<p>输出：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">999 1083 1312 3543 4194 4245 4654 5141 5341</span><br></pre></td></tr></table></figure></p>
<p>或者将基数排序提交到<a href="https://www.luogu.org/problemnew/show/P1177" target="_blank" rel="noopener">这里</a>。</p>
<h4 id="分析-analysis-1"><a href="#分析-analysis-1" class="headerlink" title="分析 analysis"></a>分析 <code>analysis</code></h4><p>先看一下如何证明基数排序。<br>假设所有数的位数都一样……<br>小排大叫：“假设？那如果不一样呢？”<br>“不一样就补<code>0</code>呗，补到所有数的位数一样为止，也不能补多，所有数的最高位不能全是<code>0</code>”<br>好，我们继续证。<br>如果所有最高位……小排你别冲动，如果所有最高位都不相同……小排！别皮了！<br>那么，肯定最高位数小的整个数就小。所以最后排完百位之后如果百位都不相等，排序自然就<code>ok</code>了。<br>当然最高位有可能是相同的，<del>小排你爽了吧~</del>所以我们之前要比后面的几位，原理嘛很简单。<br>把后面的几位分别想象成最高位，然后再带回刚才的证明思路就行了。<br>正确性证明完了，但是相信你看到上面那些代码后一定有骂人的冲动。为什么？太麻烦了。<br>这就是其中的一个缺点。<br>而且，这还是无法解决负数和小数的问题。这还是一个缺点。<br>但是解决了计数排序中最大值过大的问题。这是优点。<br>并且时间复杂度为 <strong>O(d(n+k))</strong> .<br>其中n表示有多少个数，d表示待排序列的最大位数，k表示每一位数的范围(在正常的数中范围自然是<code>10</code>.)。<br>因为用了<code>STL</code>,所以空间复杂度求解比较困难。不过一般不会炸。<br>现在来总结一下基数排序吧~<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">基数排序的优点：</span><br><span class="line">1.解决了计数排序留下的空间爆炸问题。</span><br><span class="line">2.时间复杂度降低了不少。</span><br><span class="line">缺点：</span><br><span class="line">1.代码比计数排序难懂并且复杂。</span><br><span class="line">2.还是无法解决小数与负数的问题，对数的要求仍然很高。</span><br></pre></td></tr></table></figure></p>
<p>需要注意的是，这种排序属于 <strong>稳定排序</strong><br>并且其中的位值原理是非常重要的一部分，大家需要了解。<br>因为时间复杂度的原因，这个排序经常用来卡常数。<br>好了，<code>第2关</code>也过了，好开心~~~  </p>
<h3 id="桶排序-bucket-sort"><a href="#桶排序-bucket-sort" class="headerlink" title="桶排序 bucket sort"></a>桶排序 <code>bucket sort</code></h3><p>趁小排去上厕所了，悄悄给你们科普一下桶排序。<br><del>（别问我为什么）</del><br>相信经过上面几轮关于计数的排序的洗礼后，一定对这种套路有所了解了。<br>这里简单介绍一下桶排。<br>假设说我有一个序列，每个数的取值范围都是<code>1-1000</code><br>然后再来若干个桶，比如第一个桶存<code>1-10</code>的数，第二个桶存<code>11-20</code>的数。。。<br>很显然就有<code>100</code>个桶了。<br><del> 当然第一个桶存<code>1-100</code>也无所谓，这样就是<code>10</code>个桶。 </del><br>然后分别把这几个桶用其他的排序，比如刚刚学到的计数和基数<br>以及下面要学到的冒泡排序，选择排序，快速排序，希尔排序，等等等等。<br>然后再把这些桶合在一起就<code>ok</code>了。<br>假设一共有<code>n</code>个数，<code>m</code>个桶，最大值是<code>k</code>.<br>如果可以恰好把<code>n</code>个数平均分给<code>m</code>个桶，并且对每个桶使用 <strong>快速排序</strong><br><strong>时间复杂度</strong> 是<br><code>O(n+m*n/m*log(n/m)+k)=O(n+nlog(n)-nlog(m)+k)</code>.<br>可见<code>n</code>接近于<code>m</code>话，时间复杂度是<code>O(n+k)</code>.<br>其实我们会发现如果<code>n=m</code>，这就是一个现成的 <strong>计数排序</strong> 了。<br>但事实上这是最好情况，在最坏情况<code>m=1</code>的情况下，就和一般的排序没啥区别了。<br>既然桶最多是最好情况，为何不用计数排序？<br>原因很简单，计数排序把把所有的空间都开销了，很多空间根本就没有使用。<br>而桶排序是一段一段的，能减少空间浪费率。<br>也就是减少 <strong>空间复杂度</strong><br>虽然浪费了点<strong>时间</strong>，但是节省了大量<strong>空间</strong>，这是十分划算的。<br>优缺点也很显然了。见“计数排序”。<br>还有两个缺点：排序是 <strong>不稳定排序</strong>  ，代码麻烦。<br>所以桶排序也比较罕见。<br>基于计数的排序，比较常用的，也就是<strong>计数排序</strong>了。</p>
<h2 id="基于比较的排序-comparing"><a href="#基于比较的排序-comparing" class="headerlink" title="基于比较的排序 comparing"></a>基于比较的排序 <code>comparing</code></h2><h3 id="交换排序-swapping"><a href="#交换排序-swapping" class="headerlink" title="交换排序 swapping"></a>交换排序 <code>swapping</code></h3><h4 id="冒泡排序-bubble-sort"><a href="#冒泡排序-bubble-sort" class="headerlink" title="冒泡排序 bubble sort"></a>冒泡排序 <code>bubble sort</code></h4><h5 id="概念-conception-2"><a href="#概念-conception-2" class="headerlink" title="概念 conception"></a>概念 <code>conception</code></h5><p>小排上完厕所回来了。我们来到了<code>第3关</code>。<br><code>第3关是这样的：-3333,1.131,19191919191919199119191,2314513.333,-1.13415726</code><br>由于数据很极端，满足不了 <strong><del>傲娇的</del>基于计数的排序们了。</strong><br>气得小排一直在那里画圈。嘴里还咕哝什么。<br>我思考了片刻……</p>
<p>“小排啊，别抱怨了，我有一个思路了。”<br>他赶紧过来瞅瞅我有什么新进展。<br>“你看，从小到大排序，那么是不是大的在最后啊~”<br>“嗯嗯，这不废话么”<br>“但是这句话对我接下来要讲的 <strong>异常关键</strong> ”<br>“我们可以从第一个数开始，如果第一个数&gt;第二个数，也就是”<br>“<code>a[i]&gt;a[i+1]</code>”<br>“不符合规则，我们就可以”<br>“<code>swap(a[i],a[i+1])</code>”<br>“<code>swap</code>就是交换的意思。”<br>“拿一个例子举例一下。 <del> 这关的数列太毒瘤就不拿这个了 </del>”<br>“<code>5,3,2,4,1</code>.”<br>“好了，从第一次开始：”<br>“5和3比较，发现 <strong>满足<code>a[i]&gt;a[i+1]</code>，将5,3交换。</strong>”<br>“<code>3,5,2,4,1</code>.”<br>“第二次，再看第二个和第三个：”<br>“ <strong>5&gt;2.发现满足<code>a[i]&gt;a[i+1]</code>，将5,2交换。</strong>”<br>“<code>3,2,5,4,1</code>”<br>“然后就这么变 ^ _ ^”<br>“<code>3,2,4,5,1</code>”  </p>
<p>“<code>3,2,4,1,5</code>.”<br>“OK,是不是发现第一大的数已经归位了？”<br>“像不像一个数泡泡不断地根据规则往上浮？”<br>“所以这个排序也叫冒泡排序。”<br>“我们把刚才的那些交换操作统称为‘一趟’。”<br>“接下来的几趟规则都是一样的。小排，到你了。”<br> <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure></p>
<p>“啊？到我了是么？”<br>“<code>2,3,4,1,5</code>”<br><strong>“哎呀，3和4并不满足<code>a[i]&gt;a[i+1]</code>，不交换会不会对后面有影响啊？”</strong><br>“不会的你放心吧。”我回答。<br>“<code>2,3,1,4,5</code>”<br>“哇好神奇！！！第二大的也归位了！！”<br>“嗯嗯！然后再遍历几趟~”<br>“哎，说太麻烦了……”<br>他拿来了刚才画圈的那只树枝，写下了：<br><code>2,1,3,4,5</code><br><strong>“1和3不满足<code>a[i]&gt;a[i+1]</code>，不交换。”</strong> <del>废话，顺序对了非得调乱是什么操作？</del><br>“这又是一趟~”<br><code>1,2,3,4,5</code><br>“嗯姆？？竟然真的排序成功了！”<br>“嗯。你现在已经懂了冒泡排序的精髓了。”<br>“冒泡排序的精髓是：<strong>每次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。</strong>”  </p>
<p><img src="/blog/algorithms/all_sorts/bubble.gif" alt="image"></p>
<p><img src="https://gss2.bdstatic.com/9fo3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=f469bce5077b020818c437b303b099b6/bf096b63f6246b60965c2634e6f81a4c510fa224.jpg" alt="image"></p>
<h5 id="代码-code-2"><a href="#代码-code-2" class="headerlink" title="代码 code"></a>代码 <code>code</code></h5><p>冒泡排序也是比较简单的~<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> a[<span class="number">100</span>],n;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">    <span class="comment">//以上都是读入，这里不再赘述了。</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n<span class="number">-1</span>;i++)<span class="comment">//n个数排序进行n-1次即可</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=n-i;j++)<span class="comment">//后面的数已经冒完泡，归完位了。</span></span><br><span class="line">            <span class="keyword">if</span>(a[j]&gt;a[j+<span class="number">1</span>])<span class="comment">//如果顺序错误</span></span><br><span class="line">                swap(a[j],a[j+<span class="number">1</span>]);<span class="comment">//交换</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;a[i]&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h5 id="练习-practicing-2"><a href="#练习-practicing-2" class="headerlink" title="练习 practicing"></a>练习 <code>practicing</code></h5><ul>
<li><p>基础：<br>输入：</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">10</span><br><span class="line">8 100 50 22 15 6 1 1000 999 0</span><br></pre></td></tr></table></figure>
<p>  输出：</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">0 1 6 8 15 22 50 100 999 1000</span><br></pre></td></tr></table></figure>
</li>
<li><p>挑战：<br>输入几名同学的名字和分数，按分数从小到大排序输出名字。<br>输入：</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">5</span><br><span class="line">kkksc03 100</span><br><span class="line">noip 21</span><br><span class="line">chen_zhe 99</span><br><span class="line">0x7fffffff 33</span><br><span class="line">me 0</span><br></pre></td></tr></table></figure>
<p>  输出：</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">me</span><br><span class="line">noip</span><br><span class="line">0x7ffffff</span><br><span class="line">chen_zhe</span><br><span class="line">kkksc03</span><br></pre></td></tr></table></figure>
<p>  当两人成绩相同，爱咋输出咋输出。 </p>
<ul>
<li>使用结构体</li>
<li>不使用结构体  </li>
</ul>
</li>
</ul>
<p>注：本题标程在开头的源文件中有<br>有结构体版本请查看<code>bubble_sort_prac_use_struct.cpp</code><br>无结构体版本请查看<code>bubble_sort_prac_unuse_struct.cpp</code></p>
<h5 id="分析-analysis-2"><a href="#分析-analysis-2" class="headerlink" title="分析 analysis"></a>分析 <code>analysis</code></h5><p>冒泡排序的正确性不难证明。<br>冒泡排序的核心代码是<strong>双重嵌套循环</strong>，不难看出<strong>时间复杂度</strong>是<code>O(n^2)</code>.<br>这在排序中可谓是一个十分高的复杂度了。<br>在发现冒泡排序后有许多<code>dalao</code>尝试对冒泡排序改进，但都没有成功。<br><code>Donald E. Knuth</code>（高德纳，<code>1974</code>图灵奖获得者）曾说过：</p>
<blockquote>
<p>冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。</p>
</blockquote>
<p>好啦，总结时间到了。<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">冒泡排序的优点：</span><br><span class="line">对数据要求不大，不苛刻。</span><br><span class="line">缺点：</span><br><span class="line">时间复杂度很高。</span><br></pre></td></tr></table></figure></p>
<p>高德纳<code>dalao</code>都发话了，那肯定有值得推荐的算法啊，还愣什么？<code>Go!Go!Go!</code></p>
<h4 id="快速排序-quick-sort"><a href="#快速排序-quick-sort" class="headerlink" title="快速排序 quick sort"></a>快速排序 <code>quick sort</code></h4><h5 id="概念-conception-3"><a href="#概念-conception-3" class="headerlink" title="概念 conception"></a>概念 <code>conception</code></h5><p>第<code>4</code>关的大门向我们开启了。<br>这关的要求是对<code>100000</code>个浮点数和负数及乱码七糟的东西排序。<br>嗯……我算了算，<code>O(n^2)</code>肯定不行。<br>目前，已经可以证明除了基于计数的排序外，最低复杂度是<code>O(nlogn)</code><br>啊哈！那我不就可以用快速排序了嘛！哈哈哈！<br>小排听说有复杂度更低的算法，赶紧过来，让我告诉他是什么算法，什么原理，有什么优点……<br>好的，我们现在开始吧！  </p>
<p>我们先来讨论一下这个问题：猜数这个游戏想必大家都玩过。<br>这里我们举<code>1-1000</code>的例子，让你最快猜出来，你会怎么做？<br>我相信你一定不会一个一个枚举吧……<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure></p>
<p>想必你也应该有了答案：折半猜。<br>事实上，“折半猜”确实是最优策略，在最优策略下，<strong>你一定会在<code>10</code>次内猜到这个数字。</strong><br>这个<code>10</code>是怎么来的呢？自然是<a href="https://www.codecogs.com/eqnedit.php?latex=\log_{2}{1000}" target="_blank"><img src="https://latex.codecogs.com/png.latex?\log_{2}{1000}" title="\log_{2}{1000}"></a>的结果。<br>所以，我们把一个<code>O(n)</code>的线性算法转化为<code>O(logn)</code>的对数级算法。要知道，<code>n=1e7</code>的时候，<code>O(n)</code>就有点悬了，但是<code>O(logn)</code>，只要<code>n</code>不爆<code>long long</code>，随你怎么折腾。然而<code>long long</code>的范围嘛，给你一串数：<br><code>9223372036854775807</code><br>可能你对这个数没有概念。如果把这些数量的<code>A4</code>纸叠在一起，厚度将会是九千六百亿千米。哇，太阳离地球的距离大约是一点五亿千米，<code>6400</code>个这样的距离才是这么多<code>A4</code>纸的厚度。<br>当然如果你对这个解释不满意，我给个接近科学的解释：一光年大概是<code>94605</code>亿千米，大概十份这么多<code>A4</code>纸的厚度就是一光年。也就是说，把十份这么多<code>A4</code>纸的一座极高的高塔，从高塔上方射下一束光。那么，光一年后才能到达地面。（毕竟是天文数字，误差很大，仅供参考。）<br>对于这样的优化，我们自然不能错过，而<code>O(n^2)</code>与<code>O(nlogn)</code>的关系也是如此，这样，就突破了<code>n&lt;=1000</code>的限制，<code>n</code>可以直达<code>100000</code>。  </p>
<p>然而，这一切都是二分的功劳，所以二分自然也是一种很好用的算法。二分来源于分治，分治分治，分而治之，哈哈，还有点绕口令的感觉呢。  </p>
<p>二分的概念是将一个东西分成两个部分，分然后再将每一个部分再二分，就这么一直二分下去，最后一定会分割成不能再分割的很多小单位。然后再把他们分别治理，这，就是二分的思想。不难想出，我们可以用递归实现二分。</p>
<p>快速排序也是基于二分的。来看看快排的过程：<br>假设有一个数组 <code>6 1 2 7 9 3 4 5 10 8</code>要用来排序。<br>（<code>ps</code>：本例子来自于啊哈算法）</p>
<p>“你看，我画好格子并填好数了，我站在<code>6</code>这一侧，你站在另一侧。”</p>
<p>1.设置一个<strong>基准数</strong><br>不要被这个名词吓倒，这就是个用来参照的数，为后面的步骤做准备。<del>为了方便，</del>我们把第一个数做为基准数就好啦~在这个例子中，自然是我脚下这个数<code>6</code></p>
<p>2.让基准数归到他该到的位置<code>k</code><br>什么叫“该到的位置”，简单来说，如果让基准数到达位置<code>k</code>，使基准数左面的数都小于基准数，右面的大于基准数，中间的……你应该懂得，那么怎么做呢？“来，小排，你往我这边走，如果你看到比基准数小的数就停下来。”<br><strong>切记：因为基准数在最左边，一定是小排先出发，要不然遇到某些特殊情况会<code>boom</code></strong><br>看，小排的路径是<code>8-&gt;10-&gt;5</code>，现在他来到了<code>5</code>.<br>你看，我也向小排走了走，在<code>7</code>停下了，你应该也已经猜到了，我的使命是遇到比基准数大的数就停下来。<br>好的，我们俩动用了乾坤大挪移，把脚下的数<code>swap</code>，<br>此时，数列变成了这样：<br><code>6 1 2 5 9 3 4 7 10 8</code><br>继续。“小排，你继续按照我刚才告诉你的方法走！”<br>他又走了一步，在<code>4</code>停下了。<br>我也走了一步，在<code>9</code>停下了。<br>然后。继续<code>swap.......</code><br>此时，数列变成了这样：<br><code>6 1 2 5 4 3 9 7 10 8</code><br>接着走下去，他走到了<code>3</code>，我走到了……天呐！我只顾向前走，我们俩来了个<del>亲密</del>接触。<br>这也正说明了探测完毕，我们把<code>3</code>和基准数<code>6</code>交换。<del>可以收拾收拾结束了？</del><br><code>3 1 2 5 4 6 9 7 10 8</code><br>可以看到，我们已经完成了第<code>2</code>步。那么接下来呢？  </p>
<p>3.对基准数的中间为标准进行<del>叛变政策</del>二分。<br>这个很简单，递归一下就行。<br>我们取基准数前面的部分<code>3 1 2 5 4</code>，后面的部分<code>9 7 10 8</code><br>4.接下来，分别处理第一个区域，和第二个区域。对每个区域先执行第<code>2</code>步，后执行第<code>3</code>步。</p>
<p>5.所有的数应该都当了一遍基准数并且都归了位。<br>此时，排序已经结束啦！</p>
<p>先撒个花，但是我们还没有按这个例子接着走到头，<del>这是让小排非常不爽的</del><br><code>3 1 2 5 4</code>，以<code>3</code>为基准数。<br>小排走到了<code>2</code>，而我在走动的过程撞上了小排，所以把<code>2</code>和基准数<code>3</code>交换。<br><code>2 1 3 5 4</code><br>继续二分，<code>2 1</code>和<code>5 4</code>想必我不用多说，他们都在后面那个数撞上，和基准数（前面那个数）交换。分别变成<code>1 2</code>和<code>4 5</code>，其实此时，最开始数列的前半部分就搞完了。  </p>
<p><code>1 2 3 4 5 6 9 7 10 8</code> </p>
<p>对<code>9 7 10 8</code>，还是一样的套路。自己动手模拟一下第二步把！<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">S</span><br><span class="line">l</span><br><span class="line">i</span><br><span class="line">d</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">d</span><br><span class="line">o</span><br><span class="line">w</span><br><span class="line">n</span><br><span class="line"></span><br><span class="line">t</span><br><span class="line">o</span><br><span class="line"></span><br><span class="line">s</span><br><span class="line">e</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">n</span><br><span class="line">e</span><br><span class="line">x</span><br><span class="line">t</span><br><span class="line"></span><br><span class="line">p</span><br><span class="line">a</span><br><span class="line">g</span><br><span class="line">e</span><br><span class="line">!</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br></pre></td></tr></table></figure></p>
<p>好的，模拟后应该是<code>8 7 9 10</code>，你算对了吗？<br>二分后是<code>8 7</code>和<code>9 10</code>，俩数就很简单了，最后会得到<code>7 8 9 10</code><br>和前面的一拼，<code>wonderful!</code><br><code>1 2 3 4 5 6 7 8 9 10</code>  </p>
<p>撒个花，啦啦啦啦啦~</p>
<p><img src="/blog/algorithms/all_sorts/quick.gif" alt="image"></p>
<h5 id="代码code"><a href="#代码code" class="headerlink" title="代码code"></a>代码<code>code</code></h5><p>递归思想+分治思想。<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> a[<span class="number">100005</span>],n;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">quicksort</span><span class="params">(<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(l&gt;=r) <span class="keyword">return</span> ;<span class="comment">//如果l&gt;=r了，说明探测结束，直接返回</span></span><br><span class="line">    <span class="keyword">int</span> tmp=a[l];<span class="comment">//基准数</span></span><br><span class="line">    <span class="keyword">int</span> i=l,j=r;<span class="comment">//初始化！！！！！！！for烙下的病，写这个程序找bug找了好半会才发现呵呵哒</span></span><br><span class="line">    <span class="keyword">while</span>(i!=j)<span class="comment">//我们俩没遇到的时候……</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">while</span>(a[j]&gt;=tmp&amp;&amp;i&lt;j)</span><br><span class="line">            j--;<span class="comment">//小排开始走</span></span><br><span class="line"></span><br><span class="line">        <span class="comment">//顺序很重要，一定是小排先走哦</span></span><br><span class="line">        <span class="keyword">while</span>(a[i]&lt;=tmp&amp;&amp;i&lt;j)</span><br><span class="line">            i++;<span class="comment">//我也开始走了</span></span><br><span class="line">        <span class="keyword">if</span>(i&lt;j) swap(a[i],a[j]);<span class="comment">//乾坤大挪移</span></span><br><span class="line">    &#125;</span><br><span class="line">    swap(a[l],a[i]);<span class="comment">//交换基准数和我们脚下的数        </span></span><br><span class="line">    quicksort(l,i<span class="number">-1</span>);</span><br><span class="line">    quicksort(i+<span class="number">1</span>,r);</span><br><span class="line">    <span class="keyword">return</span> ;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line"></span><br><span class="line">    quicksort(<span class="number">1</span>,n);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;a[i]&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="选择排序-selection-sort"><a href="#选择排序-selection-sort" class="headerlink" title="选择排序 selection sort"></a>选择排序 <code>selection sort</code></h3><h4 id="直接选择排序-straight-selection-sort"><a href="#直接选择排序-straight-selection-sort" class="headerlink" title="直接选择排序 straight selection sort"></a>直接选择排序 <code>straight selection sort</code></h4><h5 id="概念-conception-4"><a href="#概念-conception-4" class="headerlink" title="概念 conception"></a>概念 <code>conception</code></h5><p>这次可谓是直截了当，门上没有显示数列，仅刻有一行英文：<br><code>Use selection sort.</code><br>让我们干啥就干啥，我们没得选。  </p>
<p>“小排，你看。”<br>“好啦，我过来了。”<br>“你看，这里有一个数列。<code>2,1,3,5,4.</code>”<br>“然后呢？”<br>“我们可以直截了当的想，是不是可以遍历到一个数后，求这个数排序后的下标，让它去他应有的地方就行了？”<br>“对啊，关键是你怎么求下标。”<br>他深思熟虑了片刻。。。。<br>你也想想看，能不能想出来怎么求下标呢？<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">S</span><br><span class="line">l</span><br><span class="line">i</span><br><span class="line">d</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">d</span><br><span class="line">o</span><br><span class="line">w</span><br><span class="line">n</span><br><span class="line"></span><br><span class="line">t</span><br><span class="line">o</span><br><span class="line"></span><br><span class="line">s</span><br><span class="line">e</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">n</span><br><span class="line">e</span><br><span class="line">x</span><br><span class="line">t</span><br><span class="line"></span><br><span class="line">p</span><br><span class="line">a</span><br><span class="line">g</span><br><span class="line">e</span><br><span class="line">!</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br></pre></td></tr></table></figure></p>
<p>“我们可以每到一个数，将其和后面的数列中求出最小值，将这个最小值和他交换就行了。” 小排说道。<br><del>“妙哉，汝秀也！”</del><br>“现在我们用刚才说的那个例子来看。”<br><code>2,1,3,5,4</code><br>“首先我们的可爱的循环变量<code>i</code>到了第一个数<code>2.</code>”<br>“此时可爱的<code>j</code>向后望去，到了第二个数<code>1.</code>”<br>“发现<code>a[i]&gt;a[j]</code>，<code>swap(a[i],a[j]).</code>”<br>“<code>swap</code>是什么意思啊？” 小排突然插了一句嘴。<br>“刚才说啦，是交换的意思。你又没认真听讲。”<br>“我们继续，<code>j</code>向后继续遍历，发现没有比他小的了。”<br>此时，数列变成了：<br><code>1,2,3,5,4.</code><br>“然后我们可爱的小<code>i</code>来到了第二个数<code>2.</code>”<br>“后面没有比<code>2</code>还要小的了，所以<code>i++</code>，来到<code>3...</code>”<br>就一直这么下去，最后我们会发现数列变成了:<br><code>1,2,3,4,5.</code><br>“妙哉，妙哉！”小排大叫。</p>
<p>好了，直接选择排序我们就讲完啦~<br>真是够狠，够直接，看看这排序的英文名你就知道了。<br><img src="https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=ac41536b9016fdfacc61cebcd5e6e731/a9d3fd1f4134970a3be0b86f98cad1c8a6865dda.jpg" alt="image"></p>
<p><img src="/blog/algorithms/all_sorts/selection.gif" alt="image"></p>
<h5 id="代码-code-3"><a href="#代码-code-3" class="headerlink" title="代码 code"></a>代码 <code>code</code></h5><p>直接选择排序也很简单的~<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> a[<span class="number">10</span>],n,minnum;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        minnum=i;<span class="comment">//minnum用来存第i小的数的下标</span></span><br><span class="line">        <span class="comment">//也就是一会谁来跟a[i]换</span></span><br><span class="line">        <span class="comment">//当然默认是不换的，所以初始化为i</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=i;j&lt;=n;j++)<span class="comment">//j向后遍历</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[minnum]&gt;a[j])</span><br><span class="line">                minnum=j;</span><br><span class="line">            <span class="comment">//如果发现有比a[i]小的，就先更新</span></span><br><span class="line">            <span class="comment">//为什么不能直接swap？万一后面还有更小的？</span></span><br><span class="line">        &#125;</span><br><span class="line">        swap(a[minnum],a[i]);<span class="comment">//交换</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;a[i]&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h5 id="练习-practicing-3"><a href="#练习-practicing-3" class="headerlink" title="练习 practicing"></a>练习 <code>practicing</code></h5><p>排序：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">5</span><br><span class="line">5 3 4 2 1</span><br></pre></td></tr></table></figure></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">1 2 3 4 5</span><br></pre></td></tr></table></figure>
<p>自己敲一遍<code>code</code></p>
<h5 id="分析-analysis-3"><a href="#分析-analysis-3" class="headerlink" title="分析 analysis"></a>分析 <code>analysis</code></h5><p>分析？<del>瞎分析</del><br><del>好吧我们还是正经的分一下析</del><br>这个排序的证明嘛，首先引用小排的一句名言：</p>
<blockquote>
<p>我们可以每到一个数，将其和后面的数列中求出最小值，将这个最小值和他交换就行了。  </p>
</blockquote>
<p><del>这是名言？</del><br>这就是<strong>直接选择排序</strong>的精髓。<br>证明方法很简单：<br>假设我们来到了第一个数，然后向后寻找最小值：<br>如果找到了，替换了，第一个数就是全数列的最小值。<br>如果没找到，说明第一个数就是全数列的最小值。<br><del>反正第一个数搞完后肯定是最小值</del><br>然后我们又来到了第二个数，这时最小值已经是第一个了。<br>所以再往后找的最小值就是第二小的。<br>经过这么一趟折腾，第<code>i</code>个数就是第<code>i</code>小的数。<br>自然我们就完成了排序的目的。<br>正确性证明完了，现在来看看<del>把数万考生折磨的生不如死的</del><strong>复杂度</strong>：<br><strong>时间复杂度</strong>：双重嵌套循环，<code>O($$n^2$$)</code><br><strong>空间复杂度</strong>：<code>O(n).</code><br>其实后面排序的<strong>空间复杂度</strong>基本上都是<code>O(n)</code>.<br>哎，可惜的是这玩意儿复杂度还是很高。<br><del>带着悲痛的心情</del>总结一下直接选择排序：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">直接选择排序的优点：</span><br><span class="line">一样，对数没有特殊要求</span><br><span class="line">缺点：</span><br><span class="line">慢，比较次数多</span><br></pre></td></tr></table></figure></p>
<p><del>不过，这关还是过了，乐观一点把。</del></p>
<h4 id="堆排序-heap-sort"><a href="#堆排序-heap-sort" class="headerlink" title="堆排序 heap sort"></a>堆排序 <code>heap sort</code></h4><h5 id="概念-conception-5"><a href="#概念-conception-5" class="headerlink" title="概念 conception"></a>概念 <code>conception</code></h5><p>第<code>4</code>关过去了，我们<del>强颜欢笑</del>地到了第<code>5</code>关。<br>出乎意料的是，门上竟然又出现了<code>Selection sort!</code><br>可是，我明明记得……<br>刚进入隧道时……  </p>
<blockquote>
<p>门上还刻有一行英文：<br><code>You can&#39;t use the same kinds of sorts in two or more levels.</code><br>（每一关都要用不同种类的排序） </p>
</blockquote>
<p>不管了！<code>233</code>，我们仍然用了直接选择排序，但是门并没有开……<br>我恍然大悟，<strong>堆排序</strong>也是选择排序啊，应该用的是他。<br>说起堆排序，我们就得提到一个概念：<strong>堆</strong>。<br>“堆是什么鬼？”小排问道。<br>“堆就是一棵<strong>顺序存储</strong>的<strong>完全二叉树</strong>。完全二叉树是什么我之后会写一篇文章讲到。”<br>“没事，我知道。”<br>“嗯。<strong>堆</strong>又分为<strong>大顶堆</strong>和<strong>小顶堆</strong>。”<br>这里放一张图：<br>（注：此图来源于<a href="https://www.cnblogs.com/chengxiao/p/6129630.html" target="_blank" rel="noopener">这里</a>，感谢作者提供此图。接下来所有关于堆的<strong>静态</strong>图片都出自于此。）<br><img src="/blog/algorithms/all_sorts/heap1.png" alt=""><br>“嗯，我猜你已经想到了。大顶堆的所有根节点的关键字都大于等于其两个子节点关键字。小顶堆则反之。”<br>把它映射到数组里就是这样：<br><img src="/blog/algorithms/all_sorts/heap2.png" alt=""><br>“这个数组就代表了上上图中的<strong>大顶堆</strong>。”<br>“哇哦。”<br>“你试试用简洁明了的公式来形容一下：”<br>小排拿过树枝，写下了：<br><code>arr[i]&gt;=arr[i*2+1]&amp;&amp;arr[i]&gt;=arr[i*2+2].</code><br>“那<strong>小顶堆</strong>呢？<br>小排又写下了<br><code>arr[i]&lt;=arr[i*2+1]&amp;&amp;arr[i]&lt;=arr[i*2+2].</code><br>“好啦，基础知识咱们了解完了，接下来看<strong>堆排序</strong>是怎么操作的吧~”<br><code>Step 1.</code> 构造初始堆（将无序序列晋级为堆）<br>“先注意一下，如果我们是<strong>升序排列</strong>就采用<strong>大顶堆</strong>，反之，<strong>降序排列</strong>就是<strong>小顶堆</strong>。由于我们这里用的是升序排列，所以我们采用大顶堆。”<br>“那么怎么构造呢？”<br><img src="/blog/algorithms/all_sorts/heap3.png" alt=""><br>“假设这是初始序列，我们要把它晋级为堆。”<br>“我们从最后一个非叶子结点开始。为什么不是叶子节点？他都没有子节点了还调整个啥，浪费表情。”<br>“最后一个非叶子节点，为了表述方便，我说成‘第一个非叶子节点’。那么这个点找一下，应该是<code>6</code>.”<br>“现在开始调整，刚才说过大顶堆的定义是：”<br><code>arr[i]&gt;=arr[i*2+1]&amp;&amp;arr[i]&gt;=arr[i*2+2].</code><br>“也就是根大于等于子节点才行。这棵以<code>6</code>为根的小树就不满足了。如果<strong>要调整</strong>，则我们跟子节点较大的那个交换，那样一定可以成功。<code>ok</code>，交换完后变成了这样：”<br><img src="/blog/algorithms/all_sorts/heap4.png" alt=""></p>
<p>“继续看第二个非叶子节点。对啦，就是<code>0</code>号根节点<code>4</code>.<br>由于<code>9&gt;8</code>，根节点选择和<code>9</code>交换。嗯，就变成了这样：”<br><img src="/blog/algorithms/all_sorts/heap5.png" alt=""><br>“然后我们会<del>惊喜地</del>发现第一步调整好的小树又混乱了。<del>强颜欢笑.jpg</del>”<br>“那咋办呀？”小排焦急地说。<br>“没事，再操作一次呗。”<br>“于是这个序列变成了这样：”<br><img src="/blog/algorithms/all_sorts/heap6.png" alt=""><br>“到此，我们可爱的无序序列终于晋级成了堆。”<br>“但别急，这仅仅是<code>step 1.</code>”<br><code>Step 2.</code> 将堆顶元素与末尾元素进行交换使末尾元素最大。然后继续调整堆，反复进行交换、重建、交换。（每次都可以得到当前最大的元素）<br>“按步骤来。”<br>“首先将堆顶元素<code>9</code>和末尾元素<code>4</code>交换，然后把元素<code>9</code>剪掉。”<br><img src="/blog/algorithms/all_sorts/heap7.png" alt=""><br>“好的，我们成功取到了最大值。”<br>“再重复进行<code>Step 1</code>重建。”<br><img src="/blog/algorithms/all_sorts/heap8.png" alt=""><br>“重建完毕，继续取最大值，将其和末尾元素交换。”<br>“然后又双叒叕重建。”<br><img src="/blog/algorithms/all_sorts/heap9.png" alt=""><br>“好了，我帮你把前两大的剪完了，剩下的轮到你了。”<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">S</span><br><span class="line">l</span><br><span class="line">i</span><br><span class="line">d</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">d</span><br><span class="line">o</span><br><span class="line">w</span><br><span class="line">n</span><br><span class="line"></span><br><span class="line">t</span><br><span class="line">o</span><br><span class="line"></span><br><span class="line">s</span><br><span class="line">e</span><br><span class="line">e</span><br><span class="line"></span><br><span class="line">n</span><br><span class="line">e</span><br><span class="line">x</span><br><span class="line">t</span><br><span class="line"></span><br><span class="line">p</span><br><span class="line">a</span><br><span class="line">g</span><br><span class="line">e</span><br><span class="line">!</span><br><span class="line">|</span><br><span class="line">|</span><br><span class="line">|</span><br></pre></td></tr></table></figure></p>
<p>“如果你模拟的没有错，最终结果应该是这样的：”<br><img src="/blog/algorithms/all_sorts/heap10.png" alt=""></p>
<p>“至此我们完成了排序。”<br>小排都快睡着了，这排序算法到底有何优点？<br>请听下回分解。<br><img src="/blog/algorithms/all_sorts/heap.gif" alt=""><br>（注：此图并不是上述作者所作）</p>
<h5 id="代码-code-4"><a href="#代码-code-4" class="headerlink" title="代码 code"></a>代码 <code>code</code></h5><p>抱歉并不是这回分解，是下回。<br>上代码咯，请慢慢享用。<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> n,a[<span class="number">10</span>];</span><br><span class="line"><span class="comment">//a是待排序的数组</span></span><br><span class="line"><span class="comment">//start是从数组的哪个位置开始构建堆</span></span><br><span class="line"><span class="comment">//end则是从数组的哪个位置，后面的不截了</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">maxheap</span><span class="params">(<span class="keyword">int</span> *a,<span class="keyword">int</span> start,<span class="keyword">int</span> end)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> cur=start;<span class="comment">//当前遍历到了哪个节点</span></span><br><span class="line">    <span class="keyword">int</span> l=<span class="number">2</span>*start+<span class="number">1</span>;<span class="comment">//左儿子位置</span></span><br><span class="line">    <span class="keyword">int</span> tmp=a[start];<span class="comment">//当前节点大小</span></span><br><span class="line">    <span class="keyword">for</span>(;l&lt;=end;cur=l,l=l*<span class="number">2</span>+<span class="number">1</span>)<span class="comment">//l一直到end，每一次都对子节点着想</span></span><br><span class="line">    &#123;</span><br><span class="line"> </span><br><span class="line">        <span class="comment">//l是左儿子，r是右儿子</span></span><br><span class="line">        <span class="keyword">if</span>(l&lt;end&amp;&amp;a[l]&lt;a[l+<span class="number">1</span>])</span><br><span class="line">            l++;</span><br><span class="line">        <span class="comment">//如果右儿子更好，去取右儿子</span></span><br><span class="line">        <span class="keyword">if</span>(tmp&gt;=a[l])</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            a[cur]=a[l];</span><br><span class="line">            a[l]=tmp;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//如果已经满足了要求，调整结束</span></span><br><span class="line">        <span class="comment">//否则进行交换</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">heapsort</span><span class="params">(<span class="keyword">int</span> *a,<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=n/<span class="number">2</span><span class="number">-1</span>;i&gt;=<span class="number">0</span>;i--)</span><br><span class="line">        maxheap(a,i,n<span class="number">-1</span>);</span><br><span class="line">    <span class="comment">//进行最初的step 1，将无序序列变成堆</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=n<span class="number">-1</span>;i&gt;<span class="number">0</span>;i--)</span><br><span class="line">    &#123;</span><br><span class="line">        swap(a[<span class="number">0</span>],a[i]);<span class="comment">//交换堆顶和末尾</span></span><br><span class="line">        maxheap(a,<span class="number">0</span>,i<span class="number">-1</span>);<span class="comment">//重新建造堆</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">    heapsort(a,n);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;a[i]&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h5 id="练习-practicing-4"><a href="#练习-practicing-4" class="headerlink" title="练习 practicing"></a>练习 <code>practicing</code></h5><p>嗯…………也不是这回，下一回再见！<br>1.尝试用小根堆实现一下倒序<br>（源代码里面有，名字是<code>heap_sort_prac_</code></p>

      
    </div>
    
    
    

    <div>
          
            
<div class="my_post_copyright">
  <script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>
  
  <!-- JS库 sweetalert 可修改路径 -->
  <script src="https://cdn.bootcss.com/jquery/2.0.0/jquery.min.js"></script>
  <script src="https://unpkg.com/sweetalert/dist/sweetalert.min.js"></script>
  <p><span>本文标题:</span><a href="/blog/algorithms/all_sorts/">排序大冒险（更新ing）</a></p>
  <p><span>文章作者:</span><a href="/" title="访问 东北小蟹蟹 的个人博客">东北小蟹蟹</a></p>
  <p><span>发布时间:</span>2019年01月30日 - 00:01</p>
  <p><span>最后更新:</span>2019年03月16日 - 14:03</p>
  <p><span>原始链接:</span><a href="/blog/algorithms/all_sorts/" title="排序大冒险（更新ing）">https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/</a>
    <span class="copy-path" title="点击复制文章链接"><i class="fa fa-clipboard" data-clipboard-text="https://crab-in-the-northeast.gitee.io/blog/algorithms/all_sorts/" aria-label="复制成功！"></i></span>
  </p>
  <p><span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank" title="Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)">署名-非商业性使用-禁止演绎 4.0 国际</a> 转载请保留原文链接及作者。</p>  
</div>
<script> 
    var clipboard = new Clipboard('.fa-clipboard');
	  $(".fa-clipboard").click(function(){
      clipboard.on('success', function(){
        swal({   
          title: "",   
          text: '复制成功',
          icon: "success", 
          showConfirmButton: true
          });
	    });
    });  
</script>


          
    </div>
    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>最近东北小蟹蟹要购买一些其他的插件，要不要帮帮我呢~</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.png" alt="东北小蟹蟹 微信支付 wechat_pay">
        <p>微信支付 wechat_pay</p>
      </div>
    

    

    

  </div>
</div>

      </div>
    

    
    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束啦，东北小蟹蟹感谢您的阅读哦~-------------</div>
    
</div>

      
    </div>
    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/algorithms/" rel="tag"><i class="fa fa-tag"></i> algorithms</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/blahblahblah/disaster_of_this_blog/" rel="next" title="Disaster! My blog!">
                <i class="fa fa-chevron-left"></i> Disaster! My blog!
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
    </div>
  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录 menu
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览 overview
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/blog/images/kkksc03.gif" alt="东北小蟹蟹">
            
              <p class="site-author-name" itemprop="name">东北小蟹蟹</p>
              <p class="site-description motion-element" itemprop="description">万事开头难，中间难，结尾……更难</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/blog/archives/">
              
                  <span class="site-state-item-count">3</span>
                  <span class="site-state-item-name">日志 pos.</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/blog/categories/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">分类 cat.</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/blog/tags/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">标签 tag.</span>
                </a>
              </div>
            

          </nav>

          

          

          
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-block">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                友链区
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="https://xzdxrz.github.io/" title="兄主的仙人掌的blog" target="_blank">兄主的仙人掌的blog</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://scaft619.github.io/LTFBlog/index" title="LTF的blog" target="_blank">LTF的blog</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://apro1066.top/" title="A.pro的blog" target="_blank">A.pro的blog</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://zhantianxie.com/" title="斩天邪的blog" target="_blank">斩天邪的blog</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://aaadsgfh.github.io/" title="aaadsgfh的blog" target="_blank">aaadsgfh的blog</a>
                  </li>
                
              </ul>
            </div>
          

          
        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#前言"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#背景"><span class="nav-number">2.</span> <span class="nav-text">背景</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#冒险开始了！"><span class="nav-number">3.</span> <span class="nav-text">冒险开始了！</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#基于计数的排序-counting"><span class="nav-number">3.1.</span> <span class="nav-text">基于计数的排序 counting</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#计数排序-counting-sort"><span class="nav-number">3.1.1.</span> <span class="nav-text">计数排序 counting sort</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#概念-conception"><span class="nav-number">3.1.1.1.</span> <span class="nav-text">概念 conception</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#代码-code"><span class="nav-number">3.1.1.2.</span> <span class="nav-text">代码 code</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#练习-practicing"><span class="nav-number">3.1.1.3.</span> <span class="nav-text">练习 practicing</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#分析-analysis"><span class="nav-number">3.1.1.4.</span> <span class="nav-text">分析 analysis</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#基数排序-radix-sort"><span class="nav-number">3.1.2.</span> <span class="nav-text">基数排序 radix sort</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#概念-conception-1"><span class="nav-number">3.1.2.1.</span> <span class="nav-text">概念 conception</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#代码-code-1"><span class="nav-number">3.1.2.2.</span> <span class="nav-text">代码 code</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#练习-practicing-1"><span class="nav-number">3.1.2.3.</span> <span class="nav-text">练习 practicing</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#分析-analysis-1"><span class="nav-number">3.1.2.4.</span> <span class="nav-text">分析 analysis</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#桶排序-bucket-sort"><span class="nav-number">3.1.3.</span> <span class="nav-text">桶排序 bucket sort</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#基于比较的排序-comparing"><span class="nav-number">3.2.</span> <span class="nav-text">基于比较的排序 comparing</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#交换排序-swapping"><span class="nav-number">3.2.1.</span> <span class="nav-text">交换排序 swapping</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#冒泡排序-bubble-sort"><span class="nav-number">3.2.1.1.</span> <span class="nav-text">冒泡排序 bubble sort</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#概念-conception-2"><span class="nav-number">3.2.1.1.1.</span> <span class="nav-text">概念 conception</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#代码-code-2"><span class="nav-number">3.2.1.1.2.</span> <span class="nav-text">代码 code</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#练习-practicing-2"><span class="nav-number">3.2.1.1.3.</span> <span class="nav-text">练习 practicing</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#分析-analysis-2"><span class="nav-number">3.2.1.1.4.</span> <span class="nav-text">分析 analysis</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#快速排序-quick-sort"><span class="nav-number">3.2.1.2.</span> <span class="nav-text">快速排序 quick sort</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#概念-conception-3"><span class="nav-number">3.2.1.2.1.</span> <span class="nav-text">概念 conception</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#代码code"><span class="nav-number">3.2.1.2.2.</span> <span class="nav-text">代码code</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#选择排序-selection-sort"><span class="nav-number">3.2.2.</span> <span class="nav-text">选择排序 selection sort</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#直接选择排序-straight-selection-sort"><span class="nav-number">3.2.2.1.</span> <span class="nav-text">直接选择排序 straight selection sort</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#概念-conception-4"><span class="nav-number">3.2.2.1.1.</span> <span class="nav-text">概念 conception</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#代码-code-3"><span class="nav-number">3.2.2.1.2.</span> <span class="nav-text">代码 code</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#练习-practicing-3"><span class="nav-number">3.2.2.1.3.</span> <span class="nav-text">练习 practicing</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#分析-analysis-3"><span class="nav-number">3.2.2.1.4.</span> <span class="nav-text">分析 analysis</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#堆排序-heap-sort"><span class="nav-number">3.2.2.2.</span> <span class="nav-text">堆排序 heap sort</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#概念-conception-5"><span class="nav-number">3.2.2.2.1.</span> <span class="nav-text">概念 conception</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#代码-code-4"><span class="nav-number">3.2.2.2.2.</span> <span class="nav-text">代码 code</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#练习-practicing-4"><span class="nav-number">3.2.2.2.3.</span> <span class="nav-text">练习 practicing</span></a></li></ol></li></ol></li></ol></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        
<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">东北小蟹蟹</span>

  
</div>
<div class="powered-by">
<i class="fa fa-user-md"></i><span id="busuanzi_container_site_uv">
  本站已被<span id="busuanzi_value_site_uv"></span>位dalao访问
</span>
</div>




<div class="theme-info">
  <div class="powered-by"></div>
  <span class="post-count">博客全站共9.5k字</span>
</div>

<br>

<span id="timeDate">载入天数...</span><span id="times">载入时分秒...</span>
<script>
    var now = new Date(); 
    function createtime() { 
        var grt= new Date("01/27/2019 22:38:00");//在此处修改你的建站时间
        now.setTime(now.getTime()+250); 
        days = (now - grt ) / 1000 / 60 / 60 / 24; dnum = Math.floor(days); 
        hours = (now - grt ) / 1000 / 60 / 60 - (24 * dnum); hnum = Math.floor(hours); 
        if(String(hnum).length ==1 ){hnum = "0" + hnum;} minutes = (now - grt ) / 1000 /60 - (24 * 60 * dnum) - (60 * hnum); 
        mnum = Math.floor(minutes); if(String(mnum).length ==1 ){mnum = "0" + mnum;} 
        seconds = (now - grt ) / 1000 - (24 * 60 * 60 * dnum) - (60 * 60 * hnum) - (60 * mnum); 
        snum = Math.round(seconds); if(String(snum).length ==1 ){snum = "0" + snum;} 
        document.getElementById("timeDate").innerHTML = "东北小蟹蟹已成功存活 "+dnum+" 天 "; 
        document.getElementById("times").innerHTML = hnum + " 小时 " + mnum + " 分 " + snum + " 秒"; 
    } 
setInterval("createtime()",250);
</script>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<h1> <center> 哎呀！你竟然发现了我的秘密基地！ </center> </h1>
<br>
<center> 东北<del>大闸蟹</del>小蟹蟹要不然就是在写文章，要不然就是在优化blog，要不然就是在改hexo的<del>玄学</del>bug。。</center>


        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/blog/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/blog/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  










  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//unpkg.com/valine/dist/Valine.min.js"></script>
  
  <script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item=>{
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: false,
        appId: 'wUXkY80O0p0bNQzOiefDkv1t-gzGzoHsz',
        appKey: 'rsY5Yh4URQVUTj4VC0cf4qQh',
        placeholder: 'ヾﾉ≧∀≦)o东北小蟹蟹期待你的评论哦~',
        avatar:'mm',
        guest_info:guest,
        pageSize:'10' || 10,
    });
  </script>



  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/blog/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  

  

  

  <script type="text/javascript" src="/js/src/custom.js"></script>

  <!-- 代码块复制功能 -->
<script type="text/javascript" src="/js/src/clipboard.min.js"></script>  
<script type="text/javascript" src="/js/src/clipboard-use.js"></script>
<!-- 雪花特效 -->
<script type="text/javascript">
  var windowWidth = $(window).width();
  if (windowWidth > 480) {
    document.write('<script type="text/javascript" src="/js/src/snow.js"><\/script>');
  }
</script><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({"tex2jax":{"inlineMath":[["$","$"],["\\(","\\)"]],"skipTags":["script","noscript","style","textarea","pre","code"],"processEscapes":true},"TeX":{"equationNumbers":{"autoNumber":"AMS"}}});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->


</body>
</html>
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/clicklove.js"></script>

<!-- 崩溃欺骗 -->
<script type="text/javascript" src="/js/src/crash_cheat.js"></script>
